package com.二叉树2;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

//https://leetcode.com/explore/learn/card/data-structure-tree/134/traverse-a-tree/930/

public class 后序遍历 {
    static class Solution {
        /**
         * 过程很有意思 ，解题的过程很有意思，
         * 先画3个节点的树，发现依次添加头，右，左 节点，然后反转集合就Ok了
         * 收获，解决树问题要画图，画3个点的最简单的图，解决了这三个点的问题，再增加节点再看看。
         * @param root
         * @return
         */
        public List<Integer> postorderTraversal(TreeNode root) {
            List<Integer> list = new ArrayList<>();
            if(root == null){
                return list;
            }
            TreeNode cur = root;
            Stack<TreeNode> stack = new Stack<>();
            stack.push(cur);
           while (!stack.isEmpty()){
            TreeNode treeNode = stack.pop();
            list.add(treeNode.val);
            if(treeNode.left != null){
                stack.push(treeNode.left);
            }
            if(treeNode.right != null){
                stack.push(treeNode.right);
            }
           }
            Collections.reverse(list);
            return list;
        }

        public static void main(String[] args) {
            Solution solution = new Solution();
            List<Integer> list = solution.postorderTraversal(new TreeNode( new int[]{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}));

        }
    }
}
